【题解】 [SDOI2013]森林 主席树+启发式合并 luoguP3302 | Qiuly's blog!

【题解】 [SDOI2013]森林 主席树+启发式合并 luoguP3302

Posted on | Edited on | In | Comments:

初看题面，看到 $K$ 大我们可以想到主席树，但是连边却又符合 $LCT$ ，但是毕竟 $LCT$ 是不能支持 $K$ 大的，因为 $Splay$ 辅助树不是二叉查找树。

不过主席树我们可以大力启发式合并，合并的时候重建节点的倍增数组并且重新建立节点的权值线段树。这样子每个节点要被修改的期望次数为 $logn​$ 次，那么时间复杂度就是 $O(nlog^2n)​$ (貌似是的)，这足以让我们过这道题了。

1.主席树如何上树

上树[手动滑稽]……

首先，对于节点 $u$ 的权值线段树，$ta$ 是由 $fa[u]$ 的权值线段树继承过来的，因为只是多了一个 $u$ ，所以主席树只是多增加了 $logn$ 个节点。

既然是从父亲节点继承过来的话，那么很显然我们可以在预处理倍增数组的时候顺便将主席树建好。

Code-builld:

1
2
3
4
5
6
7
void dfs(int u,int f) {
    update(root[u],root[f],1,tmp,S(a[u]));
    fa[u][0]=f,dep[u]=dep[f]+1;
    for(int i=1;i<=LogN;++i) fa[u][i]=fa[fa[u][i-1]][i-1];
    for(int i=head[u];i;i=G[i].nxt)
        if(G[i].to!=f) dfs(G[i].to,u);
}

这个很容易理解，那么我们怎么暴力合并两颗树呢？

对于要合并的两颗树，我们选择将 $size$ 小的往 $size$ 大的并，对于给出的 $x,y$ ，我们先给 $x,y$ 连好边，然后将 $y$ 的权值线段树从 $x$ 更新，丢掉以前的。最后遍历 $y$ 的子树，更新其倍增数组和权值线段树即可。

至于 $size$ 的维护的话，我们可以找到 $x,y$ 所在的树的根。这个样子 $size$ 谁大谁小只需要判断 $x,y$ 所在的树的根的 $size$ 谁大谁小即可。我们在网下遍历 $y$ 的子树时每次都将$x$ 所在树的根的 $size$ 加一即可。

Code-merge:

1
2
3
4
5
6
7
8
9
10
11
12
13
void merge(int rt,int u,int f) {
    /*rt:x所在树的根，u:当前需要重构的节点,刚进入函数的时候为y*/
    /*f:当前需要重构的节点的父节点，刚进入函数的时候为x*/
    fa[u][0]=f,dep[u]=dep[f]+1;//更新深度
    for(int i=1;i<=LogN;++i) fa[u][i]=fa[fa[u][i-1]][i-1];
    /*更新倍增数组*/
    size[rt]++,//更新size
    sta[u]=f,//记录父亲(不是倍增数组,这是用来查询所在树的根的)
    vis[u]=true;//记录一下
    update(root[u],root[f],1,tmp,S(a[u]));//重建
    for(int i=head[u];i;i=G[i].nxt) 
        if(G[i].to!=f) merge(rt,G[i].to,u);//遍历子树
}

然后差不多了，至于 $sta$ 的话，因为要查询所在树的根，为了提高效率我们可以将其作为并查集的形式。

还有一点，对于 $vis$ 数组，实际上我们建树的时候就直接用 $merge$ 好了，$vis$ 只是用来判重而已，因为是森林，有很多树。所以说我们可以不用 $dfs$ 就将初始形态的树建好。

Code-pre:

1
2
for(int i=1;i<=n;++i)
    if(!vis[i]) {merge(i,i,0);sta[i]=i;}

最后需要注意的就是主席树的空间要开很大，差不多是 $nlog^2n$ ，因为有很多结点。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include <cmath>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

const int N=8e4+7;
const int LogN=22;
const int inf=1e9+9;

template <typename _Tp> inline void IN(_Tp&x) {
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    if(flag) x=-x;
}

int testcase,lastans,n,m,T,a[N],b[N],tmp,head[N],cnt;
int size[N],sta[N],vis[N];
struct Edge {int nxt,to;}G[N<<2];

inline int S(int x) {return lower_bound(b+1,b+1+tmp,x)-b;}
inline void add(int u,int v) {
    G[++cnt]={head[u],v},head[u]=cnt;
    G[++cnt]={head[v],u},head[v]=cnt;
}

namespace Segment_Tree {
    #define mid ((l+r)>>1)
    int root[N],tot;
    struct tree {int l,r,v;}t[N*601];
    void update(int&now,int last,int l,int r,int pos) {
        now=++tot,t[now]=t[last],t[now].v++;
        if(l==r) return;
        if(pos<=mid) update(t[now].l,t[last].l,l,mid,pos);
        else update(t[now].r,t[last].r,mid+1,r,pos);
    }
    int query(int r1,int r2,int r3,int r4,int l,int r,int k) {
        if(l==r) return l;
        int th=t[t[r1].l].v+t[t[r2].l].v-t[t[r3].l].v-t[t[r4].l].v;
        if(k<=th) return query(t[r1].l,t[r2].l,t[r3].l,t[r4].l,l,mid,k);
        else return query(t[r1].r,t[r2].r,t[r3].r,t[r4].r,mid+1,r,k-th);
    }
    #undef mid
}using namespace Segment_Tree;

int dep[N],fa[N][LogN+4];
int lca(int x,int y) {
    if(x==y)return x;
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=LogN;i>=0;--i)
        if(dep[fa[x][i]]>=dep[y]) x=fa[x][i];
    if(x==y)return x;
    for(int i=LogN;i>=0;--i)
        if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
    return fa[x][0];
}

void merge(int rt,int u,int f) {
    fa[u][0]=f,dep[u]=dep[f]+1;
    for(int i=1;i<=LogN;++i) fa[u][i]=fa[fa[u][i-1]][i-1];
    size[rt]++,
    sta[u]=f,
    vis[u]=true;
    update(root[u],root[f],1,tmp,S(a[u]));
    for(int i=head[u];i;i=G[i].nxt) 
        if(G[i].to!=f) merge(rt,G[i].to,u);
}
int find(int u) {return u==sta[u]?u:sta[u]=find(sta[u]);}

int main() {
    IN(testcase);
    IN(n),IN(m),IN(T);
    for(int i=1;i<=n;++i) 
        IN(a[i]),b[i]=a[i],sta[i]=i;
    sort(b+1,b+1+n);
    for(int i=1;i<=n;++i)
        if(b[i]!=b[i-1])b[++tmp]=b[i];
    for(int i=1;i<=m;++i) {
        int x,y;IN(x),IN(y);add(x,y);
    }
    for(int i=1;i<=n;++i)
        if(!vis[i]) {merge(i,i,0);sta[i]=i;}
    for(int i=1;i<=T;++i) {
        char op[2];int x,y,k;
        scanf("%s",op);IN(x),IN(y);
        if(op[0]=='L') {
            x^=lastans,y^=lastans;
            add(x,y);
            int a=find(x),b=find(y);
            if(size[a]<size[b])swap(x,y),swap(a,b);
            merge(a,y,x);
        } else {
            IN(k);
            x^=lastans,y^=lastans,k^=lastans;
            int lca_xy=lca(x,y);
            lastans=b[query(root[x],root[y],
                            root[lca_xy],root[fa[lca_xy][0]],1,tmp,k)];
            printf("%d\n",lastans);
        }
    }
    return 0;
}

本文标题:【题解】 [SDOI2013]森林 主席树+启发式合并 luoguP3302

文章作者:Qiuly

发布时间:2019年03月29日 - 00:00

最后更新:2019年03月30日 - 15:18

原始链接:http://qiulyblog.github.io/2019/03/29/[题解]luoguP3302/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。